NASA Technical Reports Server (NTRS) 20130000623: Computationally efficient modeling and simulation of large scale systems

II

III

illinium

I

JS008336014B1

(i2) United States Patent

Jain et al.

(io) Patent No.: US 8,336,014 B1

(45) Date of Patent: Dec. 18, 2012

(54) COMPUTATIONALLY EFFICIENT

MODELING AND SIMULATION OF LARGE
SCALE SYSTEMS

(75) Inventors: Jitesh Jain, Rajasthan (IN); Stephen F.

Cauley, West Lafayette, IN (US); Hong
Li, He nan (CN); Cheng-Kok Koh, West
Lafayette, IN (US); Venkataramanan
Balakrishnan, West Lafayette, IN (US)

(73) Assignee: Purdue Research Foundation, West
Lafayette, IN (US)

( * ) Notice: Subject to any disclaimer, the term of this

patent is extended or adjusted under 35
U.S.C. 154(b) by 204 days.

(21) Appl.No.: 12/852,942

(22) Filed: Aug. 9, 2010

6,041,170 A 3/2000

6,192,328 B1 2/2001

6,820,245 B2 11/2004

7,228,259 B2 6/2007

7,307,492 B2 12/2007

7,353,157 B2 4/2008

7,774,725 B1 * 8/2010

2003/0177458 Al 9/2003

Feldmann et al.

Kahlert et al.

Beattie et al.

Freund
Tripathi et al.

Wasynczuk et al.

Jain et al 716/106

Beattie et al.

OTHER PUBLICATIONS

Gala, K. et al., “Inductance 101 : .Analysis and Design Issues,” Proc.
Design Automation Conf., Jun. 18-21, 2001, Las Vegas, Nevada, pp.
329-334.

Beattie, M. et al., “Modeling Magnetic Coupling for On-Chip Inter-
connect,” Proc. Design Automation Conf., Jun. 18-21, 2001, Las
Vegas, Nevada, pp. 335-340.

Chen, T. H. et al., “INDUCTWISE: Inductance-Wise Interconnect
Simulator and Extractor,” Proc. Int. Conf. on Computer Aided
Design , Nov. 10-14, 2002, San Jose, California, pp. 215-220.

Chen, T.-H., et al.,“HiSIM: Hierarchical Interconnect -Centric Cir-
cuit Simulator,” Proc. Int. Conf. on Computer Aided Design , Nov.
7-11, 2004, San Jose, California, pp. 489-496.

Related U.S. Application Data

(62) Division of application No. 1 1/593,465, filed on Nov.
6, 2006, now Pat. No. 7,774,725.

(60) Provisional application No. 60/733,460, filed on Nov.
4, 2005, provisional application No. 60/740,990, filed
on Nov. 30, 2005.

(51) Int. Cl.

G06F 17/50 (2006.01)

(52) U.S. Cl 716/115; 716/106; 716/111; 703/2;

703/14

(58) Field of Classification Search 716/106,

716/111, 115; 703/2, 14
See application file for complete search history.

(56) References Cited

U.S. PATENT DOCUMENTS

5,610,833 A 3/1997 Chang etal.

5,692,158 A 11/1997 Degeneff et al.

(Continued)

Primary Examiner — Naum Levin

(74) Attorney, Agent, or Firm — Maginot, Moore & Beck
LLP

(57) ABSTRACT

A method of simulating operation of a VLSI interconnect
structure having capacitive and inductive coupling between
nodes thereof. A matrix X and a matrix Y containing different
combinations of passive circuit element values for the inter-
connect structure are obtained where the element values for
each matrix include inductance L and inverse capacitance P.
An adjacency matrix A associated with the interconnect
structure is obtained. Numerical integration is used to solve
first and second equations, each including as a factor the
product of the inverse matrix X -1 and at least one other
matrix, with first equation including X -1 Y, X -1 A, and X -1 P,
and the second equation including X -1 A and X -1 P.

9 Claims, 17 Drawing Sheets

US 8,336,014 B1

Page 2

OTHER PUBLICATIONS

Devgan, A. et al., “How to Efficiently Capture On-Chip Inductance
Effects: Introducing a New Circuit Element K ,” Proc. Int. Conf. on
Computer Aided Design , Nov. 5-9, 2000, San Jose, California, pp.
150-155.

Ji, H. et al., “SPICE Compatible Circuit Models for Partial Reluc-
tance K ,” Proc. Asia South Pacific Design Automation Conf. Jan.
27-30, 2004, Yokohama, Japan, pp. 787-792.

Lin, T. et al., “On the Efficacy of Simplified 2D On-Chip Inductance
Models,” Proc. Design Automation Conf Jun. 10-14, 2002, New
Orleans, Louisiana, pp. 757-762.

Pacelli, A, “A Local Circuit Topology for Inductive Parasitic s,” Proc.
Int. Conf. on Computer Aided Design, Nov. 10-14, 2002, San Jose,
California, pp. 208-214.

Saad, Y et al., “GMRES: A Generalized Minimal Residual Algorithm
for Solving Nonsymmetric Linear Systems,” SIAM Journal on Sci-
entific Computing , vol. 7, No. 3, Jul. 1986, pp. 856-869.

Zhao, M. et al., “Hierarchical Analysis of Power Distribution Net-
works J IEEE Trans, on Computer-Aided Design of Integrated Cir-
cuits and Systems , vol. 21, No. 2, Feb. 2002, pp. 159-168.

Zheng, H. et al., “Window-Based Susceptance Models for Large-
Scale RLC Circuit Analyses,” Proc. Design, Automation and Test in
Europe Conf, Mar. 4-8, 2002, Paris, France, pp. 628-633.

Zhong, G. et al., “On-chip Interconnect Modeling by Wire Duplica-
tion J Proc. Int. Conf. on Computer Aided Design, Nov. 10-14, 2002,
San Jose, California, pp. 341-346.

Zhong, G., et al., “On-Chip Interconnect Modeling by Wire Dupli-
cation,” TEEL Transactions on Computer-Aided Design of Integrated
Circuits and Systems, vol. 22, No. 1 1, Nov. 2003, pp. 1521-1532.
Godfrin, E.M., “A Method to Compute the Inverse of an «-Block
Tri diagonal Quasi -Hermitian Matrix,” Journal of Physics: Con-
densed Matter, vol. 3, No. 40, 1991, pp. 7843-7848.

Meurant, G., “A Review on the Inverse of Symmetric Tridiagonal and
Block Tridiagonal Matrices,” SIAM Journal on Matrix Analysis and
Applications , vol. 13, No. 3, Jul. 1992, pp. 707-728.

Nabben, R., “Decay Rates of the Inverses of Nonsymmetric
Tridiagonal and Band Matrices,” SIAM Journal on Matrix Analysis
and Applications, vol. 20, No. 3, May 1999, pp. 820-837.
Svizhenko, A., et al., “Two-Dimensional Quantum Mechanical Mod-
eling of Nanotransistors” Journal of Applied Physics, vol. 91, No. 4,
Feb. 15, 2002, pp. 2343-2354.

Ruehli, A.E., “Inductance Calculation in a Complex Integrated Cir-
cuit Environment,” IBM Journal of Research and Development , Sep.
1972, pp. 470-481.

Nagel, L.W., “SPICE2: A Computer Program to Simulate Semicon-
ductor Circuits,” Technical report, U.C. Berkeley, Memorandum No.
ERL-M520, May 9, 1975, 43 1 pages.

Bevilacqua, R., et al., “Parallel Solution of Block Tridiagonal Linear
Systems ” Linear Algebra and its Applications, vol. 104, Jun. 1988,
pp. 39-57.

Bowden, K., “A Direct Solution to the Block Tridiagonal Matrix
Inversion Problem,” International Journal of General Systems, vol.
15, No. 3, Aug. 1989, pp. 185-198.

Concus P., et al. , “On Computing INV Block Preconditionings for the
Conjugate Gradient Method,” BIT Numerical Mathematics, vol. 26,
No. 4, Dec. 1986, pp. 493-504.

Chen et al., “INDUCTWISE: Inductance-Wise Interconnect Simu-
lator and Extractor,” IEEE Transactions on Computer-Aided Design
of Integrated Circuits and Systems, vol. 22, No. 7, Jul. 2003, pp.
884-894.

Jain, J. et al., “Fast Simulation of VLSI Interconnects,” IEEE/ ACM
International Conference on Computer Aided Design, Nov. 7, 2004,
pp. 93-98, San Jose, California.

He, Z. et al., “SPIE: Sparse Partial Inductance Extraction,” Proceed-
ings of the 34th Design Automation Conference, Jun. 1997, pp.
137-140, Anaheim, California.

Zhong. G. et al., “An Adaptive Window-Based Susceptance Extrac-
tion and its Efficient Implementation,” Proceedings of the 40th
Design Automation Conference, Jun. 2003, pp. 728-731, Anaheim,
California.

* cited by examiner

U.S. Patent

Dec. 18, 2012

Sheet 1 of 17

US 8,336,014 B1

FIG. 1

IQ

Column Number

FIG. 4(c)